#include<iostream>
#include<algorithm>
#include<ctime>
#include<stdlib.h>
#include "AvlTree.h"
using namespace std;


int main()
{
    //此处为测试自行编写的FindValues函数是否具有满足题目要求的功能。
    //运行此段代码时将后面对B1至B7的测试代码注释掉。
    AvlTree<int> A;
    for(int i=0;i<9;i++){
        A.insert(i);
    }
    A.FindValues(-2,3);
    A.FindValues(6,10);  

    //定义平衡树B1至B7，使其节点个数分别为100,200,400,800,1600,3200,6400。
    AvlTree<int> B1,B2,B3,B4,B5,B6,B7;

    //对于平衡树B1的测试。
    //下面对于平衡B2至B7的测试代码均与这段代码类似。
    //改变区间内数据个数时，只需改变k1的定义和FindValues函数的区间大小即可。
    for(int i=0;i<100;i++){
        B1.insert(i);
    } 
    //设置时间数据，便于记录运行时间。
    clock_t begintime1;
    clock_t endtime1;
    double time1 = 0;
    int k1;
    srand((time(0)));  //设置随机种子，使每次调用随机函数生成的随机数不同。
    for(int j=0;j<2000;j++){
       k1 = rand() % 97;  //调用随机函数，设置区间的最小值k1范围为[0,96]。
       begintime1 = clock();
       B1.FindValues(k1,k1+4);  //区间最小值为k1,数据长度为5。
       endtime1 = clock();
       time1 += double(endtime1 - begintime1) / CLOCKS_PER_SEC;
    }
    time1 /= 2000;  


    for(int i=0;i<200;i++){
        B2.insert(i);
    }  
    clock_t begintime2;
    clock_t endtime2;
    double time2;
    int k2;
    srand((time(0)));
    for(int j=0;j<2000;j++){
       k2 = rand() % 197;
       begintime2 = clock();
       B2.FindValues(k2,k2+4);
       endtime2 = clock();
       time2 += double(endtime2 - begintime2) / CLOCKS_PER_SEC;
    }
    time2 /= 2000;     


    for(int i=0;i<400;i++){
        B3.insert(i);
    }  
    clock_t begintime3;
    clock_t endtime3;
    double time3;
    int k3;
    srand((time(0)));
    for(int j=0;j<2000;j++){
       k3 = rand() % 397;
       begintime3 = clock();
       B3.FindValues(k3,k3+4);
       endtime3 = clock();
       time3 += double(endtime3 - begintime3) / CLOCKS_PER_SEC;
    }
    time3 /= 2000;    


    for(int i=0;i<800;i++){
        B4.insert(i);
    }
    clock_t begintime4;
    clock_t endtime4;
    double time4;
    int k4;
    srand((time(0)));
    for(int j=0;j<2000;j++){
       k4 = rand() % 797;
       begintime4 = clock();
       B4.FindValues(k4,k4+4);
       endtime4 = clock();
       time4 += double(endtime4 - begintime4) / CLOCKS_PER_SEC;
    }
    time4 /= 2000;   
  

    for(int i=0;i<1600;i++){
        B5.insert(i);
    }  
    clock_t begintime5;
    clock_t endtime5;
    double time5;
    int k5;
    srand((time(0)));
    for(int j=0;j<2000;j++){
       k5 = rand() % 1597;
       begintime5 = clock();
       B5.FindValues(k5,k5+4);
       endtime5 = clock();
       time5 += double(endtime5 - begintime5) / CLOCKS_PER_SEC;
    }
    time5 /= 2000;  


    for(int i=0;i<3200;i++){
        B6.insert(i);
    } 
    clock_t begintime6;
    clock_t endtime6;
    double time6 = 0;
    int k6;
    srand((time(0)));
    for(int j=0;j<2000;j++){
       k6 = rand() % 3197;
       begintime6 = clock();
       B6.FindValues(k6,k6+4);
       endtime6 = clock();
       time6 += double(endtime6 - begintime6) / CLOCKS_PER_SEC;
    }
    time6 /= 2000; 


    for(int i=0;i<6400;i++){
        B7.insert(i);
    } 
    clock_t begintime7;
    clock_t endtime7;
    double time7 = 0;
    int k7;
    srand((time(0)));
    for(int j=0;j<2000;j++){
       k7 = rand() % 6397;
       begintime7 = clock();
       B7.FindValues(k6,k6+4);
       endtime7 = clock();
       time7 += double(endtime7 - begintime7) / CLOCKS_PER_SEC;
    }
    time7 /= 2000; 
  

    cout << "The average time of the binary tree B1 is " << time1 << "s." << endl; 
    cout << "The average time of the binary tree B2 is " << time2 << "s." << endl;  
    cout << "The average time of the binary tree B3 is " << time3 << "s." << endl;  
    cout << "The average time of the binary tree B4 is " << time4 << "s." << endl;  
    cout << "The average time of the binary tree B5 is " << time5 << "s." << endl;
    cout << "The average time of the binary tree B6 is " << time6 << "s." << endl; 
    cout << "The average time of the binary tree B7 is " << time7 << "s." << endl;

    return 0;
}